package pro1_10.pro3;

/**
 3.求子数组的最大和（数组）
 题目：
 输入一个整形数组，数组里有正数也有负数。
 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
 求所有子数组的和的最大值。要求时间复杂度为O(n)。
 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
 因此输出为该子数组的和18。
 99,100,-1000,1,2,3 => 99+100=199
 -99,-100,-1000,-1,-2,-3

 思路：
 从数组第一个开始加 如果结果是负数则放弃 (记录最大值) 重新开始加
 如果最大值比0小 就是输出最大值就行了
 */
public class Main {

    public static void main(String[] args) {
        int data[] = new int[]{1, -2, 3, 10, -4, 7, 2, -5};
        int max = 0;
        int currentSum = 0;
        int maxNum = data[0];
        for(int i=0; i<data.length; i++){
            maxNum = maxNum > data[i] ? maxNum : data[i];
            if(currentSum > max) {
                max = currentSum;
            }
            currentSum = currentSum + data[i];
            if(currentSum < 0){
                currentSum = 0;
            }
        }
        if(maxNum < 0){
            System.out.println(maxNum);
        }else {
            System.out.println(max);
        }
    }
}
